package songhq.select.advance;

/**
 * 二分查找树 简称BST 定义是 一个父节点有两个子节点，左节点的键值小于等于以自己为位置的所有的右节点，包括父节点 大于等于所有的左节点
 * 即左子树不大于几点,右子树不小于节点。 
 * 该树的结构取决于键值对存入烦人顺序，在最坏的情况下，即树极度不平衡的
 * 情况下性能是比较槽糕的
 * 
 * @author songhq
 *
 */
public class binarySearchTreeSymbolTable<Key extends Comparable<Key>, Value> {
	// 整个树的根节点
	private Node root;

	// 内部节点类,
	private class Node {
		// 键
		private Key key;
		// 值
		private Value value;
		// 左子节点
		private Node left;
		// 右子节点
		private Node right;
		// 以当前节点为根节点的子树节点的个数，即子树的大小
		private int N;

		public Node(Key key, Value value, int N) {
			this.key = key;
			this.value = value;
			this.N = N;
		}
	}

	public int size() {
		return size(root);
	}

	private int size(Node root) {
		if (root == null) {
			return 0;
		} else {
			return root.N;
		}

	}

	// 实现get(key)方法
	public Value get(Key key) {
		return get(root, key);
	}

	public Value get(Node x, Key key) {
		// 基本逻辑，查找到key返回该节点中的value，没有查找到，返回null
		if (x == null) {
			return null;
		}
		int result = key.compareTo(x.key);
		if (result > 0) {
			// key比当前节点的key大，则去右边的节点查找
			return get(x.right, key);
		} else if (result < 0) {
			return get(x.left, key);
		} else {
			return x.value;
		}
	}

	// 实现put(key,value)方法
	public void put(Key key, Value value) {
		root = put(root, key, value);
	}

	public Node put(Node x, Key key, Value value) {
		// x为null，即找到了节点该放的位置
		if (x == null) {
			return new Node(key, value, 1);
		}
		int result = key.compareTo(x.key);
		if (result > 0) {
			// 注意这里并没有return
			x.right = put(root.right, key, value);
		} else if (result < 0) {
			x.left = put(root.left, key, value);
		} else {
			x.value = value;
		}
		// 计算当前子树的节点个数使用递归
		x.N = size(x.left) + size(x.right) + 1;
		return x;// 这里最后一次必会是返回根节点。
	}
	//二分查找树的字符表的比较困难的地方是delete方法
	//首先我们实现deleteMin和deleteMax 
	public void DeleteMin() {
		//删除该根节点为树的最小键值的键值对,并要跟新根节点
		//因为二分查找树存在的标识，或者是存在的要素就是根节点
		//所以我们删除了最小值要跟新根节点，不论最小值是不是根节点
		root=deleteMin(root);
		
	}
	public Node deleteMin(Node x){
		//如果根节点为null
		if(x == null) {
			return null;
		}if(x.left == null) {
			//该节点就是最左的节点
			return x.right;
		}
		//如果不是，那一定是在左子树上，利用递归的方式跟新，删除左子树上节点后
		//跟新当前节点的x.left的值,注意这句递归前没有return 即后面的语句也会递归
		//只不过跳出递归的第一在前面就return了
		x.left = deleteMin(x.left);
		x.N = size(x.left)+size(x.right)+1;
		return x;
	}
	//因为做小节点的左子树必为null，也就是最小节点的只有一个右子节点或没有子节点
	//这对于重新构建树是比较方便的，只需要将做小节点的right交给最小节点的父节点的left,如果没有的话就return null
	//现在就谈一般的delete(key)方法
	//树中找到了这个key就删除，问题是当这个key有左右节点的时候如何重构这个树
	//这里采用后继节点的方式，
	public void delete(Key key) { 
		root = delete(root,key);
	}
	public Node delete(Node x,Key key) {
		if(x == null) {
			return null;
		}
		int result = key.compareTo(x.key);
		if(result < 0) {
			x.left = delete(x.left,key);
		}else if(result >0) {
			x.right = delete(x.right,key);
		}else {
			//找到了key
			if(x.left == null) {
				return x.right;
			}
			if(x.right == null  ) {
				return x.left;
			}
			Node tmp = x;
			//关键的地方,这里使用右后继节点
			x = min(tmp.right);
 			x.right=deleteMin(tmp.right);
 			x.left = tmp.left;
		}
		x.N = size(x.left)+size(x.right) + 1;
		return x;
	}
	public Node min(Node x) {
		if(x == null) {
			return null;
		}if(x.left == null) {
			return x;
		}
		return min(x.left);
	}
	
	

	// 简单的测试,测试通过
	public static void s(String[] args) {
		binarySearchTreeSymbolTable<String, String> bst = new binarySearchTreeSymbolTable<String, String>();
		bst.put("zhangsan","say this world is beautiful");
		bst.put("lisi", "say in this world I have many things to do,time that not full ");
		System.out.println(bst.get("lisi"));
		System.out.println(bst.get("wangwu"));
		bst.delete("lisi");
		System.out.println(bst.get("lisi"));
		
	}

}
